package LeetCode;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName DataStructure
 * @Description: TODO
 * @date ${DAT}14:24
 */
public class LeetCode198 {
    public static void main(String[] args) {
        int[]  arr = {2,1,1,2};
        System.out.println(new LeetCode198().rob(arr));
    }


    //自顶向下+记忆集搜索
    public int rob2(int[] nums){
        int[] memo = new int[nums.length];
        int res = getRes(nums,0,memo);
        return res;
    }



    /**
     * 进行递归和记忆集操作  默认是从前面偷起
     * @param nums 数组
     * @param index 下标
     * @param memo 记忆集
     * @return
     */
    public int getRes(int[] nums,int index,int[] memo){
        if (index >= nums.length - 1){//超界了偷不到
            return 0;
        }
        int res = 0;
        if (memo[index] != 0){
            return memo[index];
        }
        //这是以index下标开始偷的结果
        for (int i = index; i < nums.length; i++){
            res = Math.max(res,nums[i] + getRes(nums,i + 2,memo));
        }
        memo[index] = res;
        return res;
    }


    // 不用递归进行 双指针动态规划
    public int rob(int[] nums) {
        int curmax = 0;
        int premax = 0;
        for (int i = 0; i < nums.length;i++){
           int temp = curmax;
           curmax = Math.max(curmax,premax + nums[i]);
           premax = temp;
        }
        return curmax;
    }
}
